#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <queue>
#include <iostream>
#include <set>
#include <vector>
using namespace std;
typedef long long LL;



////3
//
////	若用双堆，若k每次都为1或n，调整双堆结构的时间复杂度为O(n)
////	若用平衡二叉树，时间复杂度也为O(n),平衡二叉树适用于查找某个数值，不适合查找第k个
//
// int main() {
//	LL n, m, sum = 0, k, left, pos;//插入位置
//	string s;
//	vector<LL>v;
//	cin >> n >> m;
//	while (n--) {
//		cin >> s >> k;
//		if (s == "I") {
//			if (k < m)continue;
//			pos = upper_bound(v.begin(), v.end(), k) - v.begin();
//			v.insert(v.begin() + pos, k);
//		}
//		else if (s == "A")
//			for (int i = 0; i < v.size(); i++)v[i] += k;
//		else if (s == "S") {
//			//二分查找去掉不合格学生，查找第一个合格的学生
//			left = lower_bound(v.begin(), v.end(), k + m) - v.begin();
//			sum += left;
//			v.erase(v.begin(), v.begin() + left);//左闭右开区间
//			for (int i = 0; i < v.size(); i++)v[i] -= k;
//		}
//		else if (s == "F")//主要时间瓶颈在F上，故可以不用平衡二叉树
//		{
//			if (k > v.size())cout << -1 << endl;
//			else cout << v[v.size() - k] << endl;
//		}
//	}
//	cout << sum << endl;
//	return 0;
//}

////2
// typedef long long LL;
// void solve(int n, const vector<LL>& weights)
//{
//	unordered_map<int, LL> sumMap;
//	LL maxSum = -0x3f3f3f3f; // 初始化为一个很小的值
//
//	for (int i = 0; i < n; ++i)
//	{
//		// 计算当前节点所在的深度
//		int depth = floor(log2(i + 1)) + 1;
//		int tmp = 0;
//		sumMap[depth] += weights[i];
//	}
//
//	for (const auto& entry : sumMap)
//	{
//		if (entry.second > maxSum)maxSum = entry.second;
//	}
//	// 收集所有具有最大权值和的深度
//	vector<int> depths;
//	for (const auto& entry : sumMap)
//	{
//		if (entry.second == maxSum)
//		{
//			depths.push_back(entry.first);
//		}
//	}
//
//	// 输出结果
//	cout << maxSum << endl;
//	sort(depths.begin(), depths.end());
//	for (size_t i = 0; i < depths.size(); ++i)
//	{
//		cout << depths[i];
//		if (i != depths.size() - 1)
//		{
//			cout << " ";
//		}
//	}
// }
//
// int main() {
//	int n;
//	cin >> n;
//	vector<LL> weights(n);
//	for (int i = 0; i < n; ++i)
//	{
//		cin >> weights[i];
//		//weights[i] += 1e5;
//	}
//	solve(n, weights);
//	return 0;
// }

// 1

 #include <iostream>
 #include <queue>
 #include <climits>
 using namespace std;

 int main() {
     int n;
     scanf("%d", &n);

     priority_queue<int> left_max_heap;
     priority_queue<int, vector<int>, greater<int>> right_min_heap;

     int current_min = INT_MAX;
     int current_max = INT_MIN;

     for (int count = 1; count <= n; ++count) {
         int num;
         scanf("%d",&num);

         // 更新当前最小值和最大值
         current_min = min(current_min, num);
         current_max = max(current_max, num);

         // 维护两个堆的平衡
         if (left_max_heap.empty() && right_min_heap.empty()) {
             left_max_heap.push(num);
         }
         else {
             if (left_max_heap.size() > right_min_heap.size()) {
                 if (num >= left_max_heap.top()) {
                     right_min_heap.push(num);
                 }
                 else {
                     int temp = left_max_heap.top();
                     left_max_heap.pop();
                     left_max_heap.push(num);
                     right_min_heap.push(temp);
                 }
             }
             else {
                 if (num <= right_min_heap.top()) {
                     left_max_heap.push(num);
                 }
                 else {
                     int temp = right_min_heap.top();
                     right_min_heap.pop();
                     right_min_heap.push(num);
                     left_max_heap.push(temp);
                 }
             }
         }

         // 输出结果
         if (count != 1) {
             cout << " ";
         }
         if (count % 2 == 1) {
             printf("%d",(current_min + current_max + left_max_heap.top()) / 3);
         }
         else {
             printf("%d", (current_min + current_max + left_max_heap.top() + right_min_heap.top()) / 4);
         }
     }
     cout << endl;
     return 0;
 }

// #include <stdio.h>
// #include <stdlib.h>
// typedef int ElemType;
// typedef struct BSTNode
//{
//     ElemType data;
//     struct BSTNode* lchild, * rchild;
// }BSTNode, * BSTree;
// BSTree CreateBST();/* �����������������ɲ���ʵ�֣�ϸ�ڲ��� */
// BSTree SearchBST(BSTree T, ElemType e)
//{
//     if (T == NULL || T->data == e)return T;
//     else if (T->data > e)return SearchBST(T->lchild, e);
//     else return SearchBST(T->rchild, e);
// }
// void Inorder(BSTree T);/* ����������ɲ���ʵ�֣�ϸ�ڲ��� */
//
// int main()
//{
//     BSTree T, result;
//     ElemType n, e;
//     T = CreateBST();
//     printf("Inorder:");    Inorder(T);    printf("\n");
//     scanf("%d", &n);
//     for (int i = 0; i < n; i++)
//     {
//         scanf("%d", &e);
//         result = SearchBST(T, e);
//         if (result) printf("%d is found\n", result->data);
//         else printf("%d is not found\n", e);
//     }
//     return 0;
// }
///* ��Ĵ��뽫��Ƕ������ */

// #include<stdio.h>
// #include<stdlib.h>
// #define MAXSIZE 100
//
// typedef struct TNode* BinTree;   /* ���������� */
// typedef char ElementType;
// struct TNode {    /* ����㶨�� */
//	ElementType Data;  /* ������� */
//	BinTree Left;   /* ָ�������� */
//	BinTree Right;   /* ָ�������� */
// };
//
//
//
// void PreorderTraversal(BinTree BT) { /* ��������������� */
//	if (BT != NULL) { /* ����Ϊ�� */
//		printf("%c", BT->Data); /* ���ʸ���� */
//		PreorderTraversal(BT->Left); /* �ݹ���������� */
//		PreorderTraversal(BT->Right); /* �ݹ���������� */
//	}
// }
//
// void InorderTraversal(BinTree BT) { /* ��������������� */
//	if (BT != NULL) { /* ����Ϊ�� */
//		InorderTraversal(BT->Left); /* �ݹ���������� */
//		printf("%c", BT->Data); /* ���ʸ���� */
//		InorderTraversal(BT->Right); /* �ݹ���������� */
//	}
// }
//
// void PostorderTraversal(BinTree BT) { /* �������ĺ������ */
//	if (BT != NULL) { /* ����Ϊ�� */
//		PostorderTraversal(BT->Left); /* �ݹ���������� */
//		PostorderTraversal(BT->Right); /* �ݹ���������� */
//		printf("%c", BT->Data); /* ���ʸ���� */
//	}
// }
////�������������������н���ֵ��һ���ַ�����@��ʾ�������������������ʾ������T
// BinTree CreatBinTree()
//{
//	ElementType ch;
//	BinTree T;
//	scanf("%c", &ch); /*����������������Ľ�㣬��������@*/
//	if (ch == '@')
//		T = NULL;
//	else {
//		T = (BinTree)maLLoc(sizeof(struct TNode));
//		T->Data = ch;
//		T->Left = CreatBinTree();
//		T->Right = CreatBinTree();
//	}
//	return T;
// }
//
// int main()
//{
//	BinTree BT;
//	BT = CreatBinTree();
//
//	if (BT == NULL) {
//		printf("\n������\n");
//	}
//	else {
//		printf("��������Ľ��Ϊ��");
//		PreorderTraversal(BT);
//		printf("\n");
//
//		printf("��������Ľ��Ϊ��");
//		InorderTraversal(BT);
//		printf("\n");
//
//		printf("��������Ľ��Ϊ��");
//		PostorderTraversal(BT);
//	}
//	return 0;
// }
///* ����������д�� */